package lc.q51_100;

/**
 * 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
 *
 * @author lgb
 * @date 2020/12/19
 **/
public class Q73 {

    public void setZeroes(int[][] matrix) {
        // 思路，遍历所有的数如果该值是0，则将行头和列头设置成0
        // 然后如果行头或者列头有0，则该值设置0
        // 对于c[0][0]，因为列也用这个，所以增加标记
        int lMax = matrix.length;
        int rMax = matrix[0].length;
        boolean flag = false;
        for (int i = 0; i < lMax; i++) {
            if (matrix[i][0] == 0) {
                flag = true;
            }
            for (int j = 1; j < rMax; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 继续遍历
        // 这里有优化方案，遍历行头，遇到0，则把对应的列都设置为0
        // 然后遍历行尾，遇到0，则把对应的行都设置为0
        // 虽然整体还是O(M*N),但是不是每个元素都扫描
        for (int i = 1; i < lMax; i++) {
            for (int j = 1; j < rMax; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 设置行头
        if (matrix[0][0] == 0) {
            for (int i = 0; i < rMax; i++) {
                matrix[0][i] = 0;
            }
        }
        // 遍历列头
        if (flag) {
            for (int i = 0; i < lMax; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
